package thired.class11_digui;

import java.util.HashMap;

public class Class09_StickersToSpellWord {
    public static int minStickers1(String[] stickers, String target){
        int ans = process1(stickers,target);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    public static int process1(String[] sticks,String target){
        if(target.length() == 0){
            return 0;
        }
        int min = Integer.MAX_VALUE;
        for (String first : sticks) {
            String rest = minus(target, first);
            if (rest.length() != target.length()) {
                min = Math.min(min, process1(sticks, rest));
            }
        }
        return min + (min == Integer.MAX_VALUE ? 0 : 1);
    }

    public static String minus(String s1,String s2){
        StringBuilder sb = new StringBuilder();
        int[] count = new int[26];
        for (char c : s1.toCharArray()) {
            count[c - 'a']++;
        }
        for (char c : s2.toCharArray()) {
            count[c - 'a']--;
        }
        for (int i = 0; i < 27; i++) {
            if(count[i] > 0){
                for (int j =  0; j < count[i]; j++) {
                    sb.append((char) i + 'a');
                }
            }
        }
        return sb.toString();
    }

    public static int minStickers3(String[] stickers, String target){
        int N = stickers.length;
        int[][] counts = new int[N][26];
        for (int i = 0; i < N; i++) {
            char[] str = stickers[i].toCharArray();
            for (char cha : str) {
                counts[i][cha - 'a']++;
            }
        }
        HashMap<String, Integer> dp = new HashMap<>();
        dp.put("", 0);
        int ans = process3(counts, target, dp);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    public static int process3(int[][] sticks,String t,HashMap<String, Integer> dp){
        if(dp.containsKey(t)){
            return dp.get(t);
        }
        char[] target = t.toCharArray();
        int[] tcount = new int[26];
        for (char c : target) {
            tcount[c - 'a']++;
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < sticks.length; i++) {
            int[] count = sticks[i];
            if(count[target[0] - 'a'] > 0){

                StringBuilder builder = new StringBuilder();
                for (int j = 0; j < 26; j++) {
                    if (tcount[j] > 0) {
                        int nums = tcount[j] - count[j];
                        for (int k = 0; k < nums; k++) {
                            builder.append((char) (j + 'a'));
                        }
                    }
                }
                String rest = builder.toString();
                min = Math.min(min, process3(sticks, rest, dp));
            }
        }
        int ans = min + (min == Integer.MAX_VALUE ? 0 : 1);
        dp.put(t,ans);
        return ans;
    }
}
